package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.flag.knowledge.KLinkedList;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 82. 删除排序链表中的重复元素II
 * https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii
 */
@KLinkedList
public class LC82_RemoveDuplicatesFromSortedListII {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(3, null)))));
        Utils.printLinkedList(head);
        Utils.printLinkedList(new Solution().deleteDuplicates(head));
    }

    /**
     *
     */
    @XOptimal
    static
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode dummy = new ListNode(Integer.MAX_VALUE, head), cur = dummy;
            while (cur.next != null && cur.next.next != null) {
                int val = cur.next.val;
                if (cur.next.next.val == val) {
                    // 循环查找相同的
                    while (cur.next != null && cur.next.val == val) {
                        cur.next = cur.next.next;
                    }
                } else {
                    cur = cur.next;
                }
            }
            return dummy.next;
        }
    }
}
